Information transmitted over a communication channel, including a tape recorder, is generally received as a combination of the original information signal and a noise component. Integrity of the information content is almost entirely preserved when the signal to noise ratio of the system is large. Accordingly, refinements in design and realization of the appropriate hardware can increase the probability of error-free transmission, theoretically up to the limits imposed by the channel itself. In order to minimize the effect of intrinsic channel limitations, various techniques are employed which ultimately require a compromise between bandwidth and information transfer rate. Various limitations imposed on the channel bandwidth, information rate, and the degree of complexity of receiving and transmitting apparatus contribute to a probable error rate.
Although redundancy is a common element among these techniques, mere repetition exacts a heavy penalty in transmission rate. For example, a single repetition reduces the information rate 50 percent and a second repetition (to implement majority logic) reduces the information rate by 662/3 percent. Other means for assuring message integrity have employed sophisticated coding techniques which permit the detection, location, and correction of errors. Among the desiderata of these coding techniques are high information rate and a capability of correcting multiple errors within any given codeword of transmitted data.
In this context a codeword of n elements results from encoding operations performed upon the elements of the original data comprising K elements to yield an encoded word ("codeword") of information having K information elements and n-K check elements. The encoded redundancy in the form of n-K check elements is then available during the decoding operations to detect and correct errors in the codeword (including all information and check elements) up to some limit or merely to detect errors up to some larger limit.
Many such codes, having distinct mathematical properties, have been studied, and mathematically efficient encoding and decoding procedures have been devised, but reduction to practice with concomitant efficiency requires a special purpose computer. For example, certain classes of codes are founded on association of each information element of a codeword with an element of a Galois field. Very briefly, the Galois field is a finite field defined by a field generator, the elements of which field may be represented as polynomials in a particular primitive field element, with coefficients in the prime subfield. If the coefficients are presented in bit-serial form with the most significant coefficient first, field elements can be considered polynomials in z, where z.sup.-1 is the delay operator.
Encoding is done by adding redundant elements to the source data elements in order to make the resulting codeword satisfy prescribed parity checks. Each prescribed parity check is formed as a weighted sum of the elements in the codeword. The result of each prescribed parity check upon decoding is generally referred to as a syndrome. In the absence of errors for a linear code, all the syndromes are zero, meaning that the weighted sum of the elements forming each parity check is zero, and the presence of errors is recognized by a nonzero syndrome. In the absence of errors for the coset code of a linear code, all the syndromes have some prescribed nonzero values, and the presence of errors is recognized by departures from the prescribed nonzero values. Cyclic codes, such as Reed-Solomon codes, are a subset of linear codes. The elements of a cyclic codeword can be associated with coefficients of a codeword polynomial. The formation of parity checks can be equated with the taking of a remainder upon division of the codeword polynomial by the code generator polynomial for the code. The locations of errors and the true value of the erroneous information elements are determined after constructing certain polynomials defined on the Galois field and finding the roots of these polynomials. An encoder and decoder are, therefore, required which have the capability of performing Galois field arithmetic.
The same parity check circuit may be used for encoding and decoding, that is, for generating parity and syndrome bytes. In encoding, the data may be taken in data blocks and associated with coefficients of what may be called a data polynomial. The formation of parity checks can be performed identically as in the case of codewords to determine whether or not the data polynomial itself is divisible by the code generator polynomial. If not, the remainder is added to the data polynomial to form the codeword polynomial. Thus the remainder, whether parity or syndrome bytes, may be referred to as a parity check. For the same reasons, the term "data block" refers to corresponding coefficients of the data polynomial, the codeword polynomial, or a received polynomial, as the case may be.
Of the error correcting codes, a particular class of such codes, separately described by Bose, Chaudhuri and Hocquenhem (thus "BCH" codes), are capable of multiple error correction. Special cases of such codes are the Reed-Solomon (RS) codes with respect to which the present invention will be described.
The Berlekamp patent includes a review of the salient aspects of coding theory, applicable to BCH codes in general and to RS codes in particular. As a general reference, Berlekamp, Algebraic Coding Theory (McGraw-Hill, 1968), is recommended. In a binary realization, such codes may be regarded as having three principal positive integer parameters, n, m, and t, where n is the total length in m-bit characters of a word of encoded information, n=2.sup.m -1, and t is the error correcting capability of the code. Assuming no fewer than 2t redundant characters or check characters, such a codeword is capable of providing sufficient informational redundancy to detect and correct any set of t or fewer independent errors within the codeword of encoded information, or to correct any set of 2t or fewer independent erasures. An erasure may be defined as an error of known location within the received codeword. The present invention is directed to correcting double errors or fewer.
The properties of an algebraic finite field may be summarized briefly. For the purposes of the present invention, a field may be informally defined as a set of elements including the null element, 0, and the unit element, a.sup.0, upon which are defined operations of addition, multiplication and division. Addition and multiplication are associative and commutative, and multiplication is distributive with respect to addition. Every element of the field has a unique negative such that the negative of a given element summed with that given element itself yields the null or 0. Further, every nonzero element has a unique reciprocal such that the product of such an element with its reciprocal yields the unit element, a.sup.0. The elements comprising the field may be considered symbolic representations of binary or ternary or q-ary numbers. The description of the invention will be understood best in terms of a field of characteristic two.
The general finite field is called the Galois field and is specified by two parameters, a prime p, and an integer m, whereby GF(p.sup.m) describes a unique finite field (the Galois field of order p.sup.m) having p.sup.m elements. In such a field all operations between elements comprising the field yield results which are again elements of the field. For example, the operation of addition carried out on elements of the finite field GF(2) is defined, modulo 2, according to relations which do not admit of a "carry". Thus, the binary addition tables are: 0+1=1+0=1 and 0+0=1+1=0. Arithmetically, this is a "carry-less" addition, sometimes referred to as half addition and more commonly denoted as the exclusive-OR (XOR). It is apparent that absence of a carry thereby limits the magnitude of the resulting sum to the finite field.
The mathematical basis of Reed-Solomon codes and decoding thereof, as discussed in greater detail in Chapter 10 of Algebraic Coding Theory is as follows:
Let a.sup.b be a primitive element in GF(2.sup.m). (Conventionally, the primitive is a power of alpha, but not having the capability of typing alpha, we use the symbol a to represent alpha. Sometimes it is termed gamma.) The code generator polynomial is defined by ##EQU2## where b, d, f and i are integers and d is the code's designed distance.
Although the particular embodiment set forth in detail herein is for 8-bit operation, a particular 4-bit field, GF(2.sup.4) or GF(16), having fewer terms, can serve as an illustrative example. This particular 4-bit Galois field is that developed by the field generator: EQU G.sub.f (z)=z.sup.4 +z+z1 (2)
with a primitive element EQU a=Oz.sup.3 +Oz.sup.2 +1z.sup.1 +Oz.sup.0. (3)
The Galois arithmetic is thus modulo z.sup.4 +z +1. The consequence of this is that there are 15 numbers in the Galois field, in addition to null, 0000, all being powers of a from 0 to 14 that can be stated as third order polynomials in the form EQU F.sub.3 z.sup.3 +F.sub.2 z.sup.2 +F.sub.1 z.sup.1 +F.sub.0 z.sup.0
where the coefficients are binary 0 or 1 as set forth in Table I:
TABLE I ______________________________________ z.sup.3 z.sup.2 z.sup.1 z.sup.0 ______________________________________ a.sup.0 = 0 0 0 1 a.sup.1 = 0 0 1 0 a.sup.2 = 0 1 0 0 a.sup.3 = 1 0 0 0 a.sup.4 = 0 0 1 1 a.sup.5 = 0 1 1 0 a.sup.6 = 1 1 0 0 a.sup.7 = 1 0 1 1 a.sup.8 = 0 1 0 1 a.sup.9 = 1 0 1 0 a.sup.10 = 0 1 1 1 a.sup.11 = 1 1 1 0 a.sup.12 = 1 1 1 1 a.sup.13 = 1 1 0 1 a.sup.14 = 1 0 0 1 ______________________________________
The cycle repeats in both directions, i.e., a.sup.15 =a.sup.0, etc., and a.sup.-1 =a.sup.14, etc. All coefficients of the data polynomial, the codeword polynomial, the received polymomial and the code generator polynomial are thus in the Galois field, in powers of the primitive a. In the example below for GF(2.sup.8) or GF(256) there are eight bits to each term, with a different field generator and primitive a.
The block length of the Reed-Solomon code is n=2.sup.m -1. The codewords consist of all polynomials of degrees less than n which are multiples of g(x). There are k information elements and h-k check elements. The code is thus RS(n,k).
Let C(x) be the transmitted codeword, divisible by g(x), ##EQU3## where i is an integer and the coefficients c.sub.i are powers of the primitive a in the Galois field. If the channel noise adds to this codeword, the error pattern is ##EQU4## and the received word is ##EQU5##
The received codeword may be passed through a re-encoder (also known as a syndrome generator) which produces as its output the remainder of the polynomial division EQU s(x)=Remainder [R(x)/g(x)]. (7)
Because C(x) is a multiple of g(x), its division thereby leaves zero remainder. Hence EQU s(x)=Remainder [E(x)/g(x)]. (8)
From such remainder may be derived the weighted power-sum symmetric functions defined by EQU S.sub.ib =s(a.sup.ib)=e(a.sup.ib) (9)
from which may be derived the location and nature of any errors, and appropriate corrections can be made, all described in the Berlekamp patent.
In order to perform such error correction, it is necessary to encode the source data into codewords and to identify errors in the recovered codewords. This is done by adding parity bytes to the bytes of source data to generate codewords satisfying certain parity checks and by identifying departures from such parity checks in the recovered codewords as syndromes.
The Berlekamp patent describes effective methods and apparatus for correcting multiple errors and has been utilized successively in correcting up to six errors in an RS(255, 243) code. However, the Berlekamp process is time consuming. At high speeds it sometimes takes longer to correct errors in a received word than to transmit the next word. This means that it is necessary to store data for later corrections, which may eventually lead to exceeding storage capacity, or to slowing down the transmission rate. Both alternatives are undesirable, as it is important to transmit as fast as possible with corrections made in real time.